package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/12 17:46
 * https://leetcode.cn/problems/possible-bipartition/
 */
public class Title886 {

    private static int UNCOLORED = 0;

    private static int RED = 1;

    private static int GREEN = 2;

    private static boolean flag;

    public static boolean possibleBipartition(int n, int[][] dislikes) {
        Map<Integer, List<Integer>> hash = new HashMap<>();
        for (int[] dis : dislikes) {
            hash.computeIfAbsent(dis[0], g -> new ArrayList<>()).add(dis[1]);
            hash.computeIfAbsent(dis[1], g -> new ArrayList<>()).add(dis[0]);
        }
        int[] team = new int[n + 1];
        flag = true;
        for (int i = 1; i <= n; i++) {
            if (team[i] == UNCOLORED) {
                dfs(hash, team, i, RED);
                if (!flag) {
                    return false;
                }
            }
        }
        return flag;
    }

    private static void dfs(Map<Integer, List<Integer>> hash, int[] team, int i, int color) {
        team[i] = color;
        int other = color == RED ? GREEN : RED;
        for (Integer nextId : hash.getOrDefault(i, new ArrayList<>())) {
            if (team[nextId] == UNCOLORED) {
                dfs(hash, team, nextId, other);
            } else if (team[nextId] != other) {
                flag = false;
                return;
            }
        }
    }

    public static void main(String[] args) {
        int[][] arr = {{1, 2}, {1, 3}, {2, 3}};
        possibleBipartition(3, arr);
    }
}
